package ch04;

import java.util.Random;

public class BinaryTree<E extends Comparable<E>> {
	protected BinaryNode<E> root;

	public BinaryTree() {
		root = null;
	}

	public BinaryTree(BinaryNode<E> node) {
		this.root = node;
	}

	public BinaryNode<E> getRoot() {
		return root;
	}
	
	public void setRoot(BinaryNode<E> node) {
		this.root = node;
	}

	public boolean isEmpty() {
		return null == root;
	}

	public static void main(String[] args) {
		BST<Integer> bst = new BST<Integer>();
		int limit = 100;
		Random random = new Random();
		for (int i = 0; i < 100; i++) {
			bst.insert(random.nextInt(limit));
		}

		BinaryNode<Integer> x = bst.min(bst.getRoot());
		System.out.println(x);
		while (null != x) {
			System.out.println("value is: " + x);
			x = bst.successor(x);
		}
	}
}

class BST<E extends Comparable<E>> extends BinaryTree<E> {
	public void insert(E element) {
		if (null == root) {
			root = new BinaryNode<E>(element);
		} else {
			insert(element, root);
		}
	}

	protected BinaryNode<E> insert(E x, BinaryNode<E> t) {
		BinaryNode<E> y = null;
		BinaryNode<E> a = new BinaryNode<E>(x);
		while (null != t) {
			y = t;
			if (x.compareTo(t.element) > 0) {
				t = t.right;
			} else {
				t = t.left;
			}
		}
		a.parent = y;
		if (null == y) {
			t = a;
		} else if (x.compareTo(y.element) > 0) {
			y.right = a;
		} else {
			y.left = a;
		}
		return a;
	}

	protected BinaryNode<E> max(BinaryNode<E> t) {
		while (null != t && null != t.right) {
			t = t.right;
		}
		return t;
	}

	protected BinaryNode<E> min(BinaryNode<E> t) {
		while (null != t && null != t.left) {
			t = t.left;
		}
		return t;
	}

	protected BinaryNode<E> predecessor(BinaryNode<E> t) {
		return null;
	}

	protected BinaryNode<E> successor(BinaryNode<E> t) {
		if (null != t) {
			if (null != t.right) {
				return min(t.right);
			} else {
				BinaryNode<E> y = t.parent;
				while (null != y && t == y.right) {
					t = y;
					y = y.parent;
				}
				return y;
			}
		}
		return null;
	}

	protected boolean remove(E x) {
		return false;
	}

	protected boolean transPlant(BinaryNode<E> source, BinaryNode<E> replacement) {
		return false;
	}
}

class BinaryNode<E extends Comparable<? super E>> {
    public BinaryNode<E> parent;
    public BinaryNode<E> left;
    public BinaryNode<E> right;

    public E element;

    public BinaryNode(E element) {
	this.element = element;
	parent = left = right = null;
    }

    public BinaryNode() {
	this(null);
    }

    public BinaryNode(E element, BinaryNode<E> parent) {
	this(element);
	this.parent = parent;
    }

    public String toString() {
	return element.toString();
    }
}